"""
归并排序：将两个或者两个以上的有序表合并成一个有序表的过程。
2-路归并： 将两个有序表合并成一个有序表的过程。最为简单常用。

"""
arr = [3, 6, 9, 4, 7, 13, 16]  
a = [0]*9
arr1 = [54, 26, 93, 17, 77, 31, 44, 55, 20]

# 1. 先实现两个 有序序列的 归并，这里设两个有序表分别存在同一列表中l[low..mid], [mid..high]。
def Merge(l, t, low, mid, high):
    """
        :param      l:排序列表（存放两个有序表）
        :param      t:将l中的记录，由小到大的并入其中
        :param      low: 第一个有序表开始位置（l 首元素）
        :param      mid: 第二个有序表开始位置（l 中间位置）
        :param      high: 第二个表结尾 （l结尾）
    """

    # 拷贝l 对应的元素到 t里来
    for i in range(low, high+1):
        t[i] = l[i]

    i = k = low
    j = mid + 1

    # 合并之后的排序，重新放回 l
    while i <= mid and j <= high:
        if t[i] < t[j]:
            l[k] = t[i]
            i += 1
        else:
            l[k] = t[j]
            j += 1
        k += 1
 
    # 将 两个有序表，其中的剩余元素，添加进 l对应的尾部
    """ 实际上这里可以使用extend()方法，或者 列表的+操作代替，但是算法就要原汁原味，我们不动用函数，只用append函数想列表里添加元素"""
    while i <= mid:
        l[k] = t[i]
        i += 1
        k += 1

    while j <= high:
        l[k] = t[j]
        j += 1
        k += 1

# print(arr)
# Merge(arr, a, 0, 3, 6)
# print(arr)
# print(a)

def Msort(l, t, low, high):
    """ 归并排序 """
    # 当只有一个元素时，一定要返回上一层
    if(low >= high): return    
    
    mid = (low+high)//2  # 注意这里 low-->mid  和 mid + 1 -->high 才是平分！   我之前写的 low --> mid - 1,   mid --> high 不是平分会报错！细节问题
    Msort(l, t, low, mid)
    Msort(l, t, mid+1, high)
    # 最小子问题，左右各有一个元素，执行排序合并
    Merge(l, t, low, mid, high)

def MergeSort(l, t):
    Msort(l, t, 0, 8)

MergeSort(arr1, a)
print(arr1)
"""
arr = [3, 6, 9, 4, 7, 13, 16]
假如取： low --> mid - 1,   mid： --> high，那么：

第一次分：
3   6   9       4   7   13  16
第二次：
3      6  9
第三次：(左边触发条件回溯)
       6 9 
       6 9
       6 9
       6 9    因为 low --> mid - 1,   mid： --> high，所以一直分不开，死递归
                栈溢出。
"""

# 请看 快排的三种实现  for while 对撞指针和 快慢指针